\section{Desarrollo}

En el presente trabajo se realizó una implementación de un algoritmo para la construcción
de un malla eléctrica, constituida por celdas cada una de cuatro resistencias de 1 Ohm por resistencia.

Dividimos el proyecto en diferentes capaz que iremos analizando a lo largo de esta sección.

\subsection{Matriz}
Implementamos una clase Matriz, la misma tiene el mismo comportamiento de una matriz algebraica
cuadrada. Como siempre trabajamos con  números reales, lo que se decidió es que la clase
sea directamente una matriz de números reales de precisión doble (\texttt{double}).

A la Matriz decidimos darle las operaciones aritméticas básicas que útiles para la resolución
del problema, además de unas operaciones extra para resolver matrices e identificar celdas.
Las mismas se detallan a continuación. Para entender los algoritmos, cuando hablemos de 
tamaño nos referiremos a la cantidad de filas o columnas de la instancia actual de la matriz.
Por ejemplo si es una matriz de $5 \times 5$ su tamaño es $5$.

\subsubsection{Representación}
Como ya fue mencionado, la matriz es una matriz cuadrada.
La representación para la misma la realizamos con un arreglo de \texttt{double}, del tamaño al cuadrado,
y cada posición del arreglo es una posición de la matriz.

\subsubsection{Operaciones Suma, Resta y Multiplicación}
Estas operaciones que realizamos lo que hacen son las operaciones aritméticas de la
suma, la resta y la multiplicación para matrices. Acá mostramos los pseudo-algoritmos de la suma y
la multiplicación.
\begin{verbatim}
Suma(Matriz a,b){
  para i en [0..tamaño)
    para j en [0..tamaño)
      matrizRes(i,j) = a(i,j) + b(i,j)
}
\end{verbatim}

\begin{verbatim}
Multiplicar(Matriz a,b){
  para i en [0..tamaño)
    filaActual[tamaño]
    para j en [0..tamaño)
      valor = 0;
      para k en [0..tamaño)
        valor=valor+ a(i,k)*b(k,j)
      filaActual[j] = valor
    matrizRes.fila(i) = filaActual
}
\end{verbatim}

\subsubsection{Resolver Sistema de Ecuaciones}
Para el tema de la resolución de sistemas de ecuaciones, teniendo en cuenta que debían tratarse de
métodos exactos, no iterativos, decidimos implementar el método de eliminación gaussiana con pivoteo parcial.

La idea de utilizar el pivoteo parcial es porque hace que el método sea mucho más estable\cite{mat,slide,comp} con lo cual el error numérico
que puede producirse es menor.

La idea del algoritmo, es ir triangulando la matriz resultante del sistema de ecuaciones, a la par de
el vector del resultado $Ax=b$. Una vez triangulada la matriz A, queda la parte de \emph{backward substitution}, donde
simplemente se resuelve el problema. A continuación damos un pseudo-algoritmo.

\begin{verbatim}
Resolver(Matriz A, Arreglo b) : Arreglo x {
  //Triangulamos A junto con b
  int i=0,j=0
  mientras i<tamaño && j<tamaño
    maxRow = i
    para k en [i+1..tamaño)
      si abs(A(k,j)) > abs(A(maxRow,j))
        maxRow = k
    si A(maxRow,j) == 0 entonces ERROR
    intercambiarFilax(A,i,maxRow)
    intercambiar(b[i],b[maxRow])
    para k en [i+1..tamaño)
      coeficiente = A(k,j)/A(i,j)
      para l en [j..tamaño)
        A(k,l) = A(k,l) - coeficiente*A(i,l)
      b[k] = b[k] - coeficiente*b[i] 
    i++ j++
  //Backward Substitution
  para k en [tamaño-1..0]
    valor = b[k]
    para l en [k+1..tamaño)
      valor = valor - A(k,l)*x[l]
    x[k] = valor/A(k,k)
}
\end{verbatim}

\subsubsection{Identificación de cada elemento}
Debido a la forma de recorrer la malla para poder obtener el sistema de ecuaciones a resolver (el cual será
explicado en las siguientes secciones) decidimos darle a la matriz una función, que dado una posición devuelve
un id, que es único para la misma. Matemáticamente podemos definirlo como:
$getId:\mathrm{R^2} \rightarrow \mathrm{R}$ inyectiva tal que $getId(i,j) = i \cdot tama$\emph{ñ}$o + j$.

\subsection{Mallas y Celdas}

\subsubsection{Introducción}
Para poder realizar distintos tipos de pruebas decidimos modelar el TAD Malla, el cual nos facilito muchas cosas a la hora de probar nuestras hipótesis. Este TAD tiene las siguientes particularidades: siempre representa a una malla \emph{válida}, tiene una función que se llama \texttt{getResistencia} la cual calcula la resistencia generada por esta malla entre las conexiones de \emph{entrada} y de \emph{salida}, las funciones que pueden cambiar el estado interno de esta malla solo lo cambian si la malla sigue siendo \emph{válida}, y además otras funciones tales como \textbf{mostrar} utilizada para mostrar la malla por consola y \texttt{show} utilizada para generar un archivo \textbf{html} mostrando la malla. Además se utilizo un simple TAD llamado \textbf{Celda} que guarda información como ubicación, si es una celda válida o no y que tipo de celda es.

\subsubsection{Representación}

Para representar esta malla decidimos utilizar una \textbf{Matriz} con valores específicos, donde cada celda de la matriz representa una celda de la malla. Dependiendo del valor de estas celdas es que hay un espacio vacío (0), una celda común (1), una celda de entrada(2), una celda de salida(3) o una celda de entrada y salida (4). Además de esta matriz, también contamos con dos celdas correspondientes a la salida y a la entrada de la malla en cuestión.

\subsubsection{Validez}

Dado que las configuraciones que podía tener uno de estos circuitos eran tan diversos, y debía cumplir varias reglas, decidimos modelar la malla de tal forma que no hubiera que pensar si la malla que uno esta construyendo es válida o no en cada oportunidad, sino que sea el TAD el que nos permita o no construir dicha malla. Para esto último se puso especial inteligencia en los \emph{constructores} y \emph{setters}.

\subsubsection{Constructores}

Los constructores del TAD permiten dejar hecha una malla válida desde el comienzo, esto significa que dado un punto de entrada y un punto de salida validos para el circuito existe un "camino" de celdas que los una. Cuando hablamos de camino queremos decir celdas que tengan en común al menos una resistencia. Es de importancia hacer notar que estos puntos de entrada y salida deben ser válidos, con esto queremos decir que el \emph{nodo} donde entra la corriente debe ser uno distinto para la entrada y para la salida.

Algunos ejemplos de condiciones iniciales:

\includegraphics[scale=0.5]{img/iomalla.pdf}
   
Notar que el ultimo gráfico muestra que un nodo del sistema no puede ser entrada y salida.

\subsubsection{Setters}

Este TAD no permite modificar la entrada y la salida una vez construido, así que los setters sólo agregan o quitan celdas en posiciones dadas. Es decir, si quitar o poner una celda en un determinado lugar rompe con la validez de la malla, esta operación no surte efecto y se devuelve un booleano con valor falso indicando que la operación no fue realizada. Para poner una celda es necesario que la misma cumpla dos cosas:
  \begin{itemize}
   \item compartir una resistencia con una celda ya existente,
    \item no obstruir una entrada o salida
  \end{itemize}
   
\includegraphics[scale=0.5]{img/setCelda.pdf}

Notar que en el caso (B) no se puede agregar una celda a esa malla ya que no tendría una resistencia en común con ninguna otra celda, y en el caso (C) tampoco se podría agregar dado que está obstruyendo una entrada o salida.

En cambio para quitar una celda (como en todo problema de construcción siempre quitar es más difícil que agregar) es necesario ver que todas las celdas sigan conectadas. 

\includegraphics[scale=0.5]{img/resetCelda.pdf}

Notar que en el caso (B) se estaría dejando desconectada a una celda de todas las demás.

Como ver que todas las celdas estuvieran conectadas no era simple definimos una función llamada \texttt{pintarConectados} que recorre la malla en forma recursiva, conectando todas las celdas que estén conectadas entre si. Entonces para poder borrar simulamos el borrado: se llama a \texttt{pintarConectados} y después chequeamos que todas las celdas sigan interconectadas aún después de borrar. En caso de éxito, se acepta el cambio, sino se deshace la última modificación y se devuelve un booleano con valor \texttt{false}. (Notar que pintarConectados tiene orden lineal, entonces borrar tiene orden lineal).

\subsubsection{Calculando la Resistencia de la Malla}

Este problema fue resuelto con una sola función llamada \texttt{getResistencia} la cual consta de varias partes en su procedimiento, pero básicamente utiliza el mismo algoritmo que uno utilizaría para calcular el sistema en forma manual. %%%%%%%%%%%%%%%%%%%%%

\subsubsection{Celdas a Corrientes}

Primero, la matriz que representa la malla se guarda en dos diccionarios (representados con arrays); luego se almacena el identificador de cada corriente que se va a utilizar en el cálculo y a que celda corresponde en la malla y viceversa.%%

En este gráfico se observa como se hacen las asignaciones de identificadores de corrientes a cada corriente.

\includegraphics[scale=0.5]{img/corrientes.pdf}

\subsubsection{Planteo de las ecuaciones}

Para cada corriente planteamos la ecuación de Kirchoff. Sabemos que, excepto para la corriente externa, toda corriente que suma $4$ veces su corriente, entonces en la celda con su id ponemos un $4$, y que por cada Celda vecina va un $-1$ en la celda de su fila correspondiente al id de la corriente de esa Celda. Después de haber terminado esto solo nos falta la última columna y la ultima fila. 

\subsubsection{Recorriendo el borde}
Para ello utilizamos fuertemente que la matriz es simétrica, y solo calculamos los coeficientes de la ultima ecuación, esto permite fácilmente saber los coeficientes de la última columna. Para calcularlos hicimos la función llamada \texttt{recorrerLaberinto} que recorre el borde de la malla viendo que celdas tienen alguna resistencia en común con la celda externa. \texttt{recorrerLaberinto} es una función que empieza en el nodo donde entra la corriente y va avanzando por el borde externo de la malla contando cuantas veces pasó por el borde de cada celda. Para hacer esto necesita saber en que celda y en que nodo de esa celda esta (NOROESTE, SUDESTE,...,etc) y con que dirección avanza.

El siguiente gráfico se muestra como se recorre la malla:

\includegraphics[scale=0.5]{img/recorrido.pdf}

En el gráfico se puede observar que dependiendo que celdas haya a continuación con respecto a la dirección actual, el sentido con que se recorre y la posición actual,  elige por que celda continuar, en que esquina situarse y que dirección tomar (en este caso se ve que en el paso anterior se avanzaba en sentido antihorario)

\includegraphics[scale=0.5]{img/proximaCelda.pdf}

Notar que la resolución para el caso en que el paso anterior venia recorriendo en sentido horario la solución es análoga. 

Eligiendo que camino tomar y hasta no estar en el nodo por donde sale la corriente, se va restando $-1$ a un arreglo que representa la ultima ecuación del sistema.

Una vez generada la matriz sólo queda resolverla, hallar el último valor e invertirlo para encontrar el valor numérico de la malla en cuestión.

%%%%%%%

\subsection{Encarando el problema}

Para ponernos a pensar cual podría ser el mejor algoritmo para solucionar el problema planteado, hicimos una investigación acerca de como afecta la distribución de las celdas en la malla eléctrica y como varía la resistencia resultante en función de la topología de la red.

Llegamos a un par de conclusiones importantes que se desarrollan en las siguientes subsecciones.


\subsubsection{Posibilidad de Convergencia en la Resistencia}

La experimentación trajo algunos resultados interesantes. En primer lugar, si bien puede resultar anti-intuitivo, nos dimos cuenta que si tenemos una malla con una celda que tiene entrada y salida en su parte superior e inferior, si se empiezan a poner celdas en fila una al lado de la otra, al principio se tiene una variación en la resistencia resultante, pero mientras más grande es la fila de celdas, dicho cambio es menor. Lo curioso del caso es que agregar celdas hacia los costados puede servir en un principio, pero limitando esto a unas pocas celdas, ya que sino al incrementar las celdas, por lo expuesto anteriormente, no se ganará resistencias sino lo único que se logrará es aumentar la cantidad de celdas. 

\subsubsection{Aproximación lineal de la resistencia}

Algo muy importante que descubrimos, es que existe una linealidad entre la cantidad de celdas en fila y la resistencia buscada. En este caso, analizamos dos sitauciones generales donde se respetaba esta linealidad.

En primer lugar vimos, es si hacemos matrices en forma de L, o sea una hilera de celdas en una columna y en la ultima posición una hilera en esa fila, poniendo la entrada y la salida en cada extremo, podemos calcular una función lineal para obtener que dimensión debe tener la malla en cuestión.

En el segundo caso, si la malla consiste en una tira de celdas en una misma fila, con la entrada y la salida en cada extremo, obtenemos otra función lineal, pero en este caso con una precisión mucho mayor.

Para poder calcular la función que se corresponde con los datos obtenidos, utilizamos el método de regresión lineal.\cite{linear}


\subsubsection{Métricas para otras aproximaciones}

Además de encarar solamente la aproximación de la resistencia resultante por la proximidad de la resistencia dada contra la obtenida, también decidimos proponer otras métricas a tener en cuenta, para poder deducir algunos patrones, e inferir ciertos modelos. Entre las métricas desarrolladas tenemos cantidad de celdas en la malla, cantidad de celdas compartidas y su promedio, la distancia entre la entrada y salida entre las que más usamos.


\subsection{Método definitivo}

Ahora nos dedicamos a explicar como en que consiste la heurística tomada para la resolución del problema.

Dada una resistencia, utilizamos una fórmula lineal para obtener el tamaño de la malla. Esta función nos da una error de aproximadamente 0.1 ohm. El resto del algoritmo lo que intenta es reducir este margen.

Entonces hasta acá lo que tenemos es una malla de tamaño fijo, que tiene en toda su primer columna celdas y en los extremos de la misma, la entrada y salida. 

Cabe aclarar que, por temas de redondeo, la resisencia resultante es siempre mayor a la dada. Luego para ir reduciendo el error, lo que se hace es ir agregando celdas, de arriba hacia abajo, en la columna siguiente. De esta manera se va a ir bajando la resistencia hasta que nos pasemos. Una vez que obtenemos un valor menor al dado, borramos la ultima celda agregada, para volver a quedar por encima de la resistencia a obtener. Y repetimos esto calculando en cada paso la nueva resistencia, hasta quedar por debajo del error o hasta que se acaben las columnas. En el peor de los casos sabemos que el error obtenido es menor a 0.1 Ohms.

\subsubsection{Pseudo-Algoritmo}

%{\scriptsize
\begin{verbatim}
calcularResistencia(double resistencia, double error): double obtenida {

  longitud = redonderArriba((res-0.375)/0.5) //parte entera de la cuenta + 1
  malla = CrearMalla(longitud) 
      //Crea una malla de tamaño 'longitud'  con toda la primer columna con celdas
  obtenida = malla.getResistencia()
  int i=0,j=1
  mientras (j<longitud) && (abs(obtenida-resistencia) > error) 
    mientras (j<longitud) && (obtenida > resistencia)
      i=0
      mientras (obtenida - resistenica > error) && (i < longitud)
        malla.agregarCelda(i,j)
        obtenida = malla.getResistencia()
        i=i+1
      j=j+1
    si (abs(obtenida-resistencia) > error)
      malla.sacarCelda(i-1,j-1)
      obtenida = malla.getResistencia()
  devolver resistencia
}
\end{verbatim}
%}
